package Array_and_String;

/*
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/clpgd/
 */

public class _21旋转矩阵 {
    public static void main(String[] args) {

        int[][] n = {{1,2,3},{4,5,6},{7,8,9}};

        rotate(n);

        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i][0]);
            System.out.print(n[i][1]);
            System.out.println(n[i][2]);
        }

    }

    public static void rotate(int[][] matrix) {
        //解题思路
        //观察题目可得：将按数组的四分之一三角形遍历中的数据进行3次交换即可完成本题的要求
        //每个数据的旋转规律：原行数变成新列数，原列数 + 新行数 = n - 1
        //要求不占据格外内存空间意味着不创建新的对象而将数据进行旋转，即原地旋转
        //可采用  A = A + B;  B = A - B;  A = A - B; 解决问题
        
        //按数组的四分之一三角形遍历
        for (int i = 0; i < matrix.length >> 1; i++) {
            for (int j = 0 + i; j < matrix.length - i - 1; j++) {
                fromto(matrix,i,j);
                fromto(matrix,matrix.length - 1 - j,i);
                fromto(matrix,matrix.length - 1 - i,matrix.length - 1 - j);
            }
        }

    }

    public static void fromto(int[][] matrix,int x,int y) {
        //旋转数据
        //A = matrix[x][y]
        //B = matrix[y][matrix.length - 1 - x]
        matrix[x][y] = matrix[x][y] + matrix[matrix.length - 1 - y][x];
        matrix[matrix.length - 1 - y][x] = matrix[x][y] - matrix[matrix.length - 1 - y][x];
        matrix[x][y] = matrix[x][y] - matrix[matrix.length - 1 - y][x];
    }


    //官方解法
    public void rotate2(int[][] matrix) {
        int n = matrix.length; // 不占用额外内存空间  指代矩阵空间  此int n 可忽略不计
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }


}
